翻訳と辞書 Words near each other ・ Quantum state ・ Quantum statistical mechanics ・ Quantum stirring, ratchets, and pumping ・ Quantum stochastic calculus ・ Quantum suicide and immortality ・ Quantum suicide and quantum immortality in fiction ・ Quantum superposition ・ Quantum system ・ Quantum t-design ・ Quantum technology ・ Quantum teleportation ・ Quantum field theory ・ Quantum field theory in curved spacetime ・ Quantum finance ・ Quantum fingerprinting ・ Quantum finite automata ・ Quantum Fireball ・ Quantum fluctuation ・ Quantum fluid ・ Quantum flux parametron ・ Quantum foam ・ Quantum Fourier transform ・ Quantum game theory ・ Quantum gate ・ Quantum Gate (video game) ・ Quantum gauge theory ・ Quantum geometry ・ Quantum graph ・ Quantum gravity ・ Quantum group Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Quantum finite automata ： ウィキペディア英語版 Quantum finite automata In quantum computing, quantum finite automata or QFA or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be defined, including ''measure-once'' and ''measure-many'' automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFA's are, in turn, special cases of geometric finite automata or topological finite automata. The automata work by accepting a finite-length string $\backslash sigma=(\backslash sigma\_0,\backslash sigma\_1,\backslash cdots,\backslash sigma\_k)$ of letters $\backslash sigma\_i$ from a finite alphabet $\backslash Sigma$, and assigning to each such string a probability $\backslash operatorname(\backslash sigma)$ indicating the probability of the automaton being in an accept state; that is, indicating whether the automaton accepted or rejected the string. The languages accepted by QFA's are not the regular languages of deterministic finite automata, nor are they the stochastic languages of probabilistic finite automata. Study of these quantum languages remains an active area of research. ==Informal description== There is a simple, intuitive way of understanding quantum finite automata. One begins with a graph-theoretic interpretation of deterministic finite automata (DFA). A DFA can be represented as a directed graph, with states as nodes in the graph, and arrows representing state transitions. Each arrow is labelled with a possible input symbol, so that, given a specific state and an input symbol, the arrow points at the next state. One way of representing such a graph is by means of a set of adjacency matrices, with one matrix for each input symbol. In this case, the list of possible DFA states is written as a column vector. For a given input symbol, the adjacency matrix indicates how any given state (row in the state vector) will transition to the next state; a state transition is given by matrix multiplication. One needs a distinct adjacency matrix for each possible input symbol, since each input symbol can result in a different transition. The entries in the adjacency matrix must be zero's and one's. For any given column in the matrix, only one entry can be non-zero: this is the entry that indicates the next (unique) state transition. Similarly, the state of the system is a column vector, in which only one entry is non-zero: this entry corresponds to the current state of the system. Let $\backslash Sigma=\backslash$ denote the set of input symbols. For a given input symbol $\backslash alpha\backslash in\backslash Sigma$, write $U\_\backslash alpha$ as the adjacency matrix that describes the evolution of the DFA to its next state. The set $\backslash$ then completely describes the state transition function of the DFA. Let ''Q'' represent the set of possible states of the DFA. If there are ''N'' states in ''Q'', then each matrix $U\_\backslash alpha$ is ''N'' by ''N''-dimensional. The initial state $q\_0\backslash in\; Q$ corresponds to a column vector with a one in the ''q''0'th row. A general state ''q'' is then a column vector with a one in the ''qth row. By abuse of notation, let ''q''0 and ''q'' also denote these two vectors. Then, after reading input symbols $\backslash alpha\backslash beta\backslash gamma\backslash cdots$ from the input tape, the state of the DFA will be given by $q\; =\; \backslash cdots\; U\_\backslash gamma\; U\_\backslash beta\; U\_\backslash alpha\; q\_0.$ The state transitions are given by ordinary matrix multiplication (that is, multiply ''q''0 by $U\_\backslash alpha$, ''etc.''); the order of application is 'reversed' only because we follow the standard application order in linear algebra. The above description of a DFA, in terms of linear operators and vectors, almost begs for generalization, by replacing the state-vector ''q'' by some general vector, and the matrices $\backslash$ by some general operators. This is essentially what a QFA does: it replaces ''q'' by a probability amplitude, and the $\backslash$ by unitary matrices. Other, similar generalizations also become obvious: the vector ''q'' can be some distribution on a manifold; the set of transition matrices become automorphisms of the manifold; this defines a topological finite automaton. Similarly, the matrices could be taken as automorphisms of a homogeneous space; this defines a geometric finite automaton. Before moving on to the formal description of a QFA, there are two noteworthy generalizations that should be mentioned and understood. The first is the non-deterministic finite automaton (NFA). In this case, the vector ''q'' is replaced by a vector which can have more than one entry that is non-zero. Such a vector then represents an element of the power set of ''Q''; its just an indicator function on ''Q''. Likewise, the state transition matrices $\backslash$ are defined in such a way that a given column can have several non-zero entries in it. After each application of $\backslash$, though, the column vector ''q'' must be renormalized so that it only contains zeros and ones. Equivalently, the multiply-add operations performed during component-wise matrix multiplication should be replaced by Boolean and-or operations, that is, so that one is working with a ring of characteristic 2. A well-known theorem states that, for each DFA, there is an equivalent NFA, and vice versa. This implies that the set of languages that can be recognized by DFA's and NFA's are the same; these are the regular languages. In the generalization to QFA's, the set of recognized languages will be different. Describing that set is one of the outstanding research problems in QFA theory. Another generalization that should be immediately apparent is to use a stochastic matrix for the transition matrices, and a probability vector for the state; this gives a probabilistic finite automaton. The entries in the state vector must be real numbers, positive, and sum to one, in order for the state vector to be interpreted as a probability. The transition matrices must preserve this property: this is why they must be stochastic. Each state vector should be imagined as specifying a point in a simplex; thus, this is a topological automaton, with the simplex being the manifold, and the stochastic matrices being linear automorphisms of the simplex onto itself. Since each transition is (essentially) independent of the previous (if we disregard the distinction between accepted and rejected languages), the PFA essentially becomes a kind of Markov chain. By contrast, in a QFA, the manifold is complex projective space $\backslash mathbbP^N$, and the transition matrices are unitary matrices. Each point in $\backslash mathbbP^N$ corresponds to a quantum-mechanical probability amplitude or pure state; the unitary matrices can be thought of as governing the time evolution of the system (viz in the Schrödinger picture). The generalization from pure states to mixed states should be straightforward: A mixed state is simply a measure-theoretic probability distribution on $\backslash mathbbP^N$. A worthy point to contemplate is the distributions that result on the manifold during the input of a language. In order for an automaton to be 'efficient' in recognizing a language, that distribution should be 'as uniform as possible'. This need for uniformity is the underlying principle behind maximum entropy methods: these simply guarantee crisp, compact operation of the automaton. Put in other words, the machine learning methods used to train hidden Markov models generalize to QFA's as well: the Viterbi algorithm and the forward-backward algorithm generalize readily to the QFA. Although the study of QFA was popularized in the work of Kondacs and Watrous in 1997〔 and later by Moore and Crutchfeld, they were described as early as 1971, by Ion Baianu.〔I. Bainau, "(Organismic Supercategories and Qualitative Dynamics of Systems )" (1971), Bulletin of Mathematical Biophysics, 33 pp.339-354.〕〔I. Baianu, "Categories, Functors and Quantum Automata Theory" (1971). The 4th Intl.Congress LMPS, August-Sept.1971〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quantum finite automata」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.